package com.leetcode.二叉树;

import com.leetcode.公共.TreeNode;

/**
 * 给定一颗二叉搜索树，判断其是否是一个有效的二叉搜索树
 * 给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
 * <p>
 * 有效 二叉搜索树定义如下：
 * <p>
 * 节点的左子树只包含 小于 当前节点的数。
 * 节点的右子树只包含 大于 当前节点的数。
 * 所有左子树和右子树自身必须也是二叉搜索树。
 * <p>
 * 链接：https://leetcode-cn.com/problems/validate-binary-search-tree
 */
public class 验证二叉搜索树 {
    // last为空，处理第一个节点
    private Integer last = null;

    /**
     * 思路一：使用中序遍历，数据一定是从小到大排列
     *
     * @param root
     * @return
     */
    public boolean isValidBST(TreeNode root) {
        if (root == null) return true;
        // 如果左边已经返回false 就没有必要继续
        if (!isValidBST(root.left)) return false;

        if (last != null && root.val < last) return false;
        last = root.val;

        // 同理，如果右边已经返回false 就没有必要继续
        if (!isValidBST(root.right)) return false;

        return true;
    }

    // 思路二：
    // 在遍历每一个节点的同时，指定节点的取值范围（此节点的父节点和祖父节点决定上界和下界）
    // 假设这个节点是其父节点的的左子树，那么这个节点就必须小于他的父节点(父节点的值为上界)，父节点是祖父节点的左子树或者右子树决定其下界
    // 是其父节点的右子树，那么这个节点就必须大于他的父节点(父节点的值为下界)，父节点是祖父节点的左子树或者右子树决定其上界
    // 这种方式适合每一种遍历方式
}
